package 二叉树;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<T extends Comparable<T>> {
    private BinaryNode<T> root;

    public BinaryTree() {
        this.root = null;
    }

    public BinaryTree(BinaryNode<T> root) {
        this.root = root;
    }

    //判空
    public boolean isEmpty() {
        return this.root == null;
    }

    //插入操作
    public void insert(T x) {
        if (x != null) {
            //x作为根节点  原来的节点作为根节点左孩子
            this.root = new BinaryNode<>(x, this.root, null);
        }
    }

    public BinaryNode<T> insert(BinaryNode<T> p, boolean left, T x) {
        if (x == null || p == null) {
            return null;
        }
        if (left) {
            return p.left = new BinaryNode<>(x, p.left, null);
        } else {
            return p.right = new BinaryNode<>(x, null, p.right);
        }
    }

    //删除节点
    public void remove(BinaryNode<T> p, boolean left) {
        if (p != null) {
            p.left = null;
        } else {
            p.right = null;
        }
    }

    public void clear() {
        this.root = null;
    }


    //二叉树的拷贝
    BinaryTree(BinaryTree<T> bitree) {
        this.root = copy(bitree.root);

    }

    private BinaryNode<T> copy(BinaryNode<T> root) {
        if (root == null) {
            return null;
        }
        //拷贝根节点  中
        BinaryNode<T> q = new BinaryNode<>(root.data);
        q.left = copy(root.left);
        q.right = copy(root.right);
        return q;
    }

//先根遍历


//中根遍历


//后根遍历

//    public boolean equals(Object obj) {
//        //判断是否指向同一个地址
//        if (obj == this) {
//            return true;
//        }
//        if (obj instanceof BinaryTree<?>) {
//            BinaryTree ob = (BinaryTree) obj;
//            //比较是否相等
//            if (this.equals(this.root, ob.root)) {
//                return true;
//            } else {
//                return false;
//            }
//        }
//        return false;
//    }

    static Integer minValue = null;

    public static <T extends Comparable<T>> T min(BinaryTree<T> bitree) {
        if (bitree.root == null) {
            return null;
        }
        return bitree.min(bitree.root);

    }

    private T min(BinaryNode<T> root) {
        if (root == null) {
            return null;
        }
        T min = root.data;
        T leftMin = min(root.left);
        if (leftMin != null && leftMin.compareTo(min) < 0) {
            min = leftMin;
        }
        T rightMin = min(root.right);
        if (rightMin != null && rightMin.compareTo(min) < 0) {
            min = rightMin;
        }
        return min;
    }


    //采用前序遍历的方式
//    public static boolean equals(BinaryNode root, BinaryNode obj) {
//        if (root == null && obj == null) {
//            return true;
//        }
//        if (root == null || obj == null) {
//            return false;
//        }
//        if (root.data != obj.data) {
//            return false;
//        }
//        return equals(root.left, obj.left) && equals(root.right, obj.right);
//    }
//public boolean equals(BinaryNode<T> root, BinaryNode<T> obj) {
//    if (root == null && obj == null) {
//        return true;
//    }
//    if (root == null || obj == null) {
//        return false;
//    }
//    if (!root.data.equals(obj.data)) {
//        return false;
//    }
//    return equals(root.left, obj.left) && equals(root.right, obj.right);
//}
//递归求高度
    public int count() {
        //返回节点的个数
        return count(this.root);
    }

    public int count(BinaryNode<T> root) {
        //返回in节点的个数
        if (root == null) {
            return 0;
        }
        int left = count(root.left);
        int right = count(root.right);
        return left + right + 1;
    }

    public int level(T key) {
        //使用递归的方法
        return dgLevel(key, root, 1);
    }

    public int height() {
        //返回树的高度
        return height(this.root);
    }

    private int height(BinaryNode<T> root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public void preorder() {
        preorder(this.root);
    }

    private void preorder(BinaryNode<T> root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public int dgLevel(T key, BinaryNode root, int level) {
        if (root == null) {
            return 0;
        }
        if (root.data.equals(key)) {
            return level;
        }
        int leftLevel = dgLevel(key, root.left, level + 1);
        if (leftLevel != 0) {
            return leftLevel;
        }
        return dgLevel(key, root.right, level + 1);
    }

// 非递归查找方法
//public int level(T key) {
//    if (root == null) {
//        return -1;
//    }
//    // 栈保存节点以及它们对应的层级
//    Stack<Object[]> stack = new Stack<>();
//    stack.push(new Object[]{root, 1});
//
//    while (!stack.isEmpty()) {
//        Object[] nodeInfo = stack.pop();
//        BinaryNode<T> node = (BinaryNode<T>) nodeInfo[0];
//        int currentLevel = (int) nodeInfo[1];
//
//        //找到节点 返回值
//        if (node.data.equals(key)) {
//            return currentLevel;
//        }
//
//        if (node.right != null) {
//            stack.push(new Object[]{node.right, currentLevel + 1});
//        }
//        if (node.left != null) {
//            stack.push(new Object[]{node.left, currentLevel + 1});
//        }
//    }
//    return -1;  // 如果没有找到key，返回-1
//}

    //构造完全二叉树
    public static <T extends Comparable<T>> BinaryTree<T> createComplete(T[] arr) {
        if (arr == null || arr.length == 0) {
            return new BinaryTree<>();
        }
        BinaryTree<T> tree = new BinaryTree<>();
        tree.root = new BinaryNode<>(arr[0]);
        Queue<BinaryNode<T>> queue = new LinkedList<>();
        queue.offer(tree.root);
        int i = 1;
        while (i < arr.length) {
            BinaryNode<T> current = queue.poll();
            if (i < arr.length) {
                current.left = new BinaryNode<>(arr[i++]);
                queue.offer(current.left);
            }
            if (i < arr.length) {
                current.right = new BinaryNode<>(arr[i++]);
                queue.offer(current.right);
            }
        }
        return tree;
    }

    public static void main(String[] args) {
        Integer[] arr1 = {8, 2, 5, 4, 5, 6, 1, 8, 9};
        BinaryTree tree1 = createComplete(arr1);
        System.out.println(min(tree1));
        System.out.println(tree1.count());
    }
}
